package com.lql.BSTTree;

/**
 * 二叉排序树
 */
public class BinarySortTreeDemo {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};
        BinarySortTree binarySortTree = new BinarySortTree();
        for (int j : arr) {
            BinarySortTreeNode binarySortTreeNode = new BinarySortTreeNode(j);
            binarySortTree.addNode(binarySortTreeNode);
        }
        binarySortTree.listBSTTree();
//        System.out.println(binarySortTree.findParentNode(1));
        System.out.println("__________________");
        binarySortTree.delNode(7);
        binarySortTree.delNode(5);
        binarySortTree.delNode(3);
        binarySortTree.delNode(10);
        binarySortTree.delNode(9);
        binarySortTree.delNode(2);
        binarySortTree.delNode(1);
        binarySortTree.delNode(12);
        binarySortTree.listBSTTree();
        System.out.println(binarySortTree.getRoot());
    }
}

/**
 * 管理二叉排序树
 */
class BinarySortTree {
    private BinarySortTreeNode root;//根节点

    /**
     * 返回根节点
     *
     * @return 根节点
     */
    public BinarySortTreeNode getRoot() {
        return root;
    }

    public void setRoot(BinarySortTreeNode root) {
        this.root = root;
    }

    /**
     * 添加节点
     *
     * @param node 待添加节点
     */
    public void addNode(BinarySortTreeNode node) {
        if (root == null) {
            //空树
            root = node;
            return;
        }
        root.addNode(node);
    }

    /**
     * 遍历树
     */
    public void listBSTTree() {
        if (root == null) {
            //空树
            System.out.println("树为空，无法遍历");
            return;
        }
        root.listBSTTree();
    }

    /**
     * 查找节点
     *
     * @param value 节点value值
     * @return 找到则返回当前节点，否则返回空
     */
    public BinarySortTreeNode finNode(int value) {
        if (root == null) {
            //空树
            System.out.println("树为空，查找失败");
        }
        return root.finNode(value);
    }

    /**
     * 查找指定节点的父节点
     *
     * @param value 待查找节点的value值
     * @return 返回待查找节点的父节点
     */
    public BinarySortTreeNode findParentNode(int value) {
        if (root == null) {
            //空树
            System.out.println("树为空，父节点查找失败");
        }

        return root.findParentNode(value);
    }

    /**
     * 删除节点
     *
     * @param value 待删除结点的值
     */
    public void delNode(int value) {
        if (root == null) {
            //空树
            System.out.println("树为空，删除失败");
        }
        if (root.value == value) {
            //待删除节点为根节点
            if (root.leftNode == null && root.rightNode == null) {
                //只有一个根节点
                root = null;
                return;
            } else if (root.leftNode != null && root.rightNode != null) {
                //左右子树都存在
                root.delNode(value);
            } else {
                //除根节点，只存在一个节点
                if (root.leftNode != null) {
                    //左子树存在
                    root = root.leftNode;
                } else {
                    root = root.rightNode;
                }
            }
            return;
        }
        root.delNode(value);
    }
}

/**
 * 二叉排序树的节点类
 */
class BinarySortTreeNode {
    public int value;//表示是节点中存储的节点信息
    public BinarySortTreeNode leftNode;//左节点
    public BinarySortTreeNode rightNode;//右节点

    public BinarySortTreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "BinarySortTreeNode{" +
                "value=" + value +
                '}';
    }

    /**
     * 二叉排序中添加节点
     *
     * @param node 待添加的节点
     */
    public void addNode(BinarySortTreeNode node) {
        if (node == null) {
            System.out.println("节点为空，无法添加");
            return;
        }
        if (node.value < this.value) {
            //待添加的节点值小于当前节点，添加到左子树上
            if (this.leftNode == null) {
                //左子树为空，直接添加
                this.leftNode = node;
                return;
            }
            //不为空则直接递归左子树，添加节点
            this.leftNode.addNode(node);
        } else {
            //待添加的节点值小于等于当前节点，添加到右子树上
            if (this.rightNode == null) {
                //右子树为空，直接添加
                this.rightNode = node;
                return;
            }
            //不为空则直接递归右子树，添加节点
            this.rightNode.addNode(node);
        }
    }

    /**
     * 中遍历显示排序二叉树
     */
    public void listBSTTree() {
        if (this.leftNode != null) {
            //递归左子树
            this.leftNode.listBSTTree();
        }
        System.out.println(this.value);
        if (this.rightNode != null) {
            //递归右子树
            this.rightNode.listBSTTree();
        }
    }

    /**
     * 查找节点
     *
     * @param value 节点value值
     * @return 找到则返回当前节点，否则返回空
     */
    public BinarySortTreeNode finNode(int value) {
        if (this.value == value) {
            return this;
        }
        if (this.value > value) {
            //递归左子树
            if (this.leftNode != null) {
                //左递归查找
                return this.leftNode.finNode(value);
            } else {
                //左子树为空,未找到
                return null;
            }
        } else {
            //递归右子树
            if (this.rightNode != null) {
                //右递归查找
                return this.rightNode.finNode(value);
            } else {
                //右子树为空,未找到
                return null;
            }
        }
    }

    /**
     * 查找指定节点的父节点
     *
     * @param value 待查找节点的value值
     * @return 返回待查找节点的父节点
     */
    public BinarySortTreeNode findParentNode(int value) {
        if ((this.leftNode != null && this.leftNode.value == value) ||
                (this.rightNode != null && this.rightNode.value == value)) {
            return this;
        } else {
            if (this.value > value && this.leftNode != null) {
                //左递归查找
                return this.leftNode.findParentNode(value);
            } else if (this.value <= value && this.rightNode != null) {
                //右递归查找
                return this.rightNode.findParentNode(value);
            } else {
                //左右节点都为空，只存在根节点
                return null;
            }
        }
    }

    /**
     * 删除左子树上最大值并返回最大值
     *
     * @param node 节点
     * @return 左子树上的最大值
     */
    public int delLeftMaxNode(BinarySortTreeNode node) {
        //获取当前节点的左子树
        BinarySortTreeNode leftNode = node.leftNode;
        //遍历左子树的右子树的最右节点，即为最大值
        while (leftNode.rightNode != null) {
            leftNode = leftNode.rightNode;
        }
        //删除左子树上的最大节点
        delNode(leftNode.value);
        //返回被删除节点的值
        return leftNode.value;
    }

    /**
     * 删除节点
     *
     * @param value 待删除结点的值
     */
    public void delNode(int value) {
        //当前节点
        BinarySortTreeNode binarySortTreeNode = finNode(value);
        //父节点
        BinarySortTreeNode parentNode = findParentNode(value);
        if (binarySortTreeNode == null) {
            //未找到待删除结点
            return;
        }
        if (binarySortTreeNode.leftNode == null && binarySortTreeNode.rightNode == null) {
            //待删除节点为叶子节点
            if (parentNode.leftNode == binarySortTreeNode) {
                //待删除结点为左节点
                parentNode.leftNode = null;
            }
            if (parentNode.rightNode == binarySortTreeNode) {
                //待删除结点为右节点
                parentNode.rightNode = null;
            }
        } else if (binarySortTreeNode.leftNode != null && binarySortTreeNode.rightNode != null) {
            //左右子树都存在
            binarySortTreeNode.value = delLeftMaxNode(binarySortTreeNode);
        } else {
            //左右子树只存在一个
            if (binarySortTreeNode.leftNode != null) {
                //左子树存在
                if (parentNode.leftNode == binarySortTreeNode) {
                    //待删除结点为父节点的左子树
                    parentNode.leftNode = binarySortTreeNode.leftNode;
                }
                if (parentNode.rightNode == binarySortTreeNode) {
                    //待删除结点为父节点的右子树
                    parentNode.rightNode = binarySortTreeNode.leftNode;
                }
            } else {
                //右子树存在
                if (parentNode.leftNode == binarySortTreeNode) {
                    //待删除结点为父节点的左子树
                    parentNode.leftNode = binarySortTreeNode.rightNode;
                }
                if (parentNode.rightNode == binarySortTreeNode) {
                    //待删除结点为父节点的右子树
                    parentNode.rightNode = binarySortTreeNode.rightNode;
                }
            }
        }
    }
}
